1. Field of the Invention
This invention relates in general to the field of data processing in computers, and more particularly to a method for locating a significant set bit in a binary data entity.
2. Description of the Related Art
Present day computer systems operate on binary data entities. Instructions and associated data for the computer systems are encoded into binary formats ranging from standard formats to those formats which are entirely specific to a given software program.
In some formats, the combination of all of the bits in a given data entity may represent a piece of information, such as a character or a number. In other formats, each of the bits in a data entity may individually represent a piece of information. Furthermore, the position of a given bit within the data entity may reflect a priority or sequence of the given bit relative to the remaining bits in the data entity.
In view of the above, a common operation accomplished by a computer system is examining a data entity to locate a particular bit set to a specific logic state. Many computer instruction sets include instructions to test the state of specified bits within a data entity. Even more prevalent, though, are instructions whose function is to locate a most significant or a least significant logical one bit. The x86 instruction set has two such instructions: Bit Scan Forward (BSF) and Bit Scan Reverse (BSR). The BSF instruction directs a computer to locate the least significant logical one bit in a source data entity and provide an output operand containing its position within the source data entity. The BSR instruction directs a computer to locate the most significant logical one bit in a source data entity and provide an output operand containing its position within the source data entity.
The architecture for execution of the BSF and BSR instructions is fixed by the syntax of the instructions; however, the process by which a given computer system locates a significant bit and outputs its position is not predetermined. Some present day microprocessors employ a bit-wide scan method that tests each bit in order and increments/decrements an associated bit position index to reflect the position currently being tested. Other microprocessors have improved upon the bit-wide scan method by initially testing byte-wide samples of the data entity in order until a byte having a set bit is encountered. Once the byte having the set bit is found, then the method decreases the sample size to converge upon the specific location within the byte that contains the set bit. Like the bit-wide method, the byte-wide method adjusts an associated bit position index by amounts corresponding to the size of the test sample to reflect the approximate location of the significant set bit. For example, use of the bit-wide method to locate a least significant set bit in position 16 of a 32-bit data entity would require approximately 17 iterations. Use of the byte-wide method would require roughly six iterations.
The number of iterations required for these methods to complete on a given computer system are directly proportional to the associated execution time for the instructions. For this reason, a bit scan method that requires 1,000 iterations is judged by those skilled in the art as being much less desirable than another bit scan method that requires only ten iterations to complete.
While the byte-wide method indeed represents a considerable improvement over the bit-wide method, particularly in these times when 32-bit data entities are the norm, one skilled in the art will appreciate that both of the methods are inappropriate for use in searching data entities comprising many bits. This is because both methods exhibit linear growth in the number of required iterations to complete as data entity size increases. The number of iterations required for the bit-wide method to complete is proportional to the number of bits in the data entity. The number of iterations required for the byte-wide method to complete is proportional to the number of bytes in the data entity. More specifically, the bit-wide method would require 1,024 iterations to locate a least significant set bit in position 1,023 of a 1,024-bit data entity.
Historically, data entity sizes have grown, not linearly, but exponentially. And while advances in integrated circuit scaling technologies have enabled microprocessors to run at much greater speeds, much of the increase in speed has been relegated to execution of more complex logic circuits within a microprocessor. As a result, speed increases still cannot overcome the limitations imposed by linear scan methods.
Therefore, what is needed is a method for locating a significant set bit in a data entity that does not exhibit linear growth in the number of iterations to complete. In addition, what is needed is a bit scan method that exhibits only logarithmic growth in the number of iterations required to locate a significant set bit.